package com.lw.leetcode.linked;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23. 合并K个升序链表
 *
 * @Author liw
 * @Date 2021/5/19 13:07
 * @Version 1.0
 */
public class MergeKLists {

    public static void main(String[] args) {
        MergeKLists test = new MergeKLists();
        ListNode[] arr = {ListNode.getInstance3(), ListNode.getInstance4(), ListNode.getInstance5(),null};
        ListNode listNode = test.mergeKLists(arr);
        System.out.println(listNode);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode f = new ListNode(0);
        int length = lists.length;
        if (length == 0) {
            return null;
        }
        if (length == 1) {
            return lists[0];
        }
        ListNode[] arr = new ListNode[length];
        int end = -1;
        for (ListNode list : lists) {
            if (list != null) {
                arr[++end] = list;
            }
        }
        if (end == -1) {
            return null;
        }

        for(int i = ((end + 1) >> 1) - 1; i >= 0; i--){
            sort(arr, i, end);
        }
        ListNode item = f;
        while (end != -1) {
            item.next = arr[0];
            item = item.next;
            if (item.next == null) {
                arr[0] = arr[end--];
            } else {
                arr[0] = item.next;
            }
            sort(arr, 0, end);
        }
        return f.next;
    }


    private void sort (ListNode[] arr, int st, int end) {
        int l = (st << 1) + 1;
        if (l > end) {
            return;
        }
        l = l + 1 <= end ? (arr[l].val < arr[l + 1].val ? l : l + 1) : l;
        if (arr[l].val < arr[st].val ) {
            ListNode item = arr[l];
            arr[l] = arr[st];
            arr[st] = item;
            sort(arr, l, end);
        }
    }


    public int kthSmallest(int[][] matrix, int k) {

        PriorityQueue<int[]> pq = new PriorityQueue<>(( a,  b) -> a[0] - b[0]);
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            int[] now = pq.poll();
            if (now[2] != n - 1) {
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }



}
